package name.huzhenbo.java.algorithm.graph;

import name.huzhenbo.java.collection.Stack;

import java.util.List;

class Topology {
    private Graph graph;
    private int[] vexEarliest;
    private int[] vexLatest;
    private int count;
    private Stack<Integer> sortedVexesStack;


    public Topology(Graph graph) {
        this.graph = graph;
        vexEarliest = new int[graph.vertexNum()];
        vexLatest = new int[graph.vertexNum()];
        sortedVexesStack = new Stack<Integer>();
    }

    /**
     * Sort the topological graph, and get the vexEarliest for each point, which means earliest happen time for each point.
     */
    public void sort() {
        Graph graph = Graph.newInstance(this.graph);
        System.out.println("Topological sort......");
        while (graph.deletedVertexNum() < graph.vertexNum()) {
            List<Integer> vexesWithoutIn = graph.vexesWithoutIn();
            for (int vex : vexesWithoutIn) {
                count++;
                for (int w = graph.firstAdjVex(vex); w >= 0; w = graph.nextAdjVex(vex, w)) {
                    if (vexEarliest[vex] + graph.weight(vex, w) > vexEarliest[w]) {
                        vexEarliest[w] = vexEarliest[vex] + graph.weight(vex, w);
                    }
                }
                sortedVexesStack.push(vex);
                graph.remove(vex);
                System.out.println(vex);
            }
        }
        if (count < graph.vertexNum()) {
            throw new RuntimeException("This is not a topological graph!");
        }
    }

    public void criticalPath() {
        sort();
        for (int i = 0; i < vexEarliest.length; i++) vexLatest[i] = vexEarliest[i];

        // get the vexLatest for each point, which means the latest happen time for each point.
        while (!sortedVexesStack.empty()) {
            int w = sortedVexesStack.pop();
            for (int v : graph.vexesTo(w)) {
                int t = vexLatest[w] - graph.weight(v, w);
                if (t > vexLatest[v]) {
                    vexLatest[v] = t;
                }
            }
        }
        vexLatest[0] = 0;

        // Print out one of critical paths.
        // Critical path is where the vexEarliest = vexLatest
        System.out.println("Critical path....");

        int i = 0;
        while (i >= 0) {
            System.out.println(i);
            int w = graph.firstAdjVex(i);
            for (; w >= 0; w = graph.nextAdjVex(i, w)) {
                if (vexEarliest[w] == vexLatest[w]) {
                    break;
                }
            }
            if (w < 0)
                i = -1;
            else i = w;
        }
    }
}
